package com.atguigu.greedy;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 广播问题
 */
public class BroadcastAreaProblem {
    public static void main(String[] args) {
        String[] k1Arr=new String[]{"北京", "上海", "天津"};
        String[] k2Arr=new String[]{"广州", "北京", "深圳"};
        String[] k3Arr=new String[]{"成都", "上海", "杭州"};
        String[] k4Arr=new String[]{"上海", "天津"};
        String[] k5Arr=new String[]{"杭州", "大连"};

        Map<String,Set<String>> broadcast2AreaMap=new HashMap<>();
        putBroadcastInfo(broadcast2AreaMap,"k1",k1Arr);
        putBroadcastInfo(broadcast2AreaMap,"k2",k2Arr);
        putBroadcastInfo(broadcast2AreaMap,"k3",k3Arr);
        putBroadcastInfo(broadcast2AreaMap,"k4",k4Arr);
        putBroadcastInfo(broadcast2AreaMap,"k5",k5Arr);

        Collection<String> minBroadcasts = calcMinBroadcasts(broadcast2AreaMap);
        System.out.println(minBroadcasts);


    }

    public static Collection<String> calcMinBroadcasts(Map<String, Set<String>> broadcast2AreasMap){

        // 获取所有区域
        Set<String> allAreaSet = allAreas(broadcast2AreasMap);

        List<String> resultBroadcastList=new ArrayList<>();
        // 根据未覆盖区域集合,找到覆盖区域数量最多的广播站, 并遍历
        String maxAreaBroadcast=null;
        int maxAreaSize=0;
        // 此处使用tempArea,主要是为了保留原始数据. 如果不要求保留原始数据, 则不用tempSet也可以, 查询速度还会更快.
        Set<String> tempAreas=new HashSet<>();
        while(!allAreaSet.isEmpty()){
            for (String broadcast : broadcast2AreasMap.keySet()) {
                Set<String> eachAreas = broadcast2AreasMap.get(broadcast);
                tempAreas.addAll(eachAreas);
                tempAreas.retainAll(allAreaSet);
                // 贪心算法体现贪心的地方
                if(tempAreas.size()>maxAreaSize){
                    maxAreaSize=tempAreas.size();
                    maxAreaBroadcast=broadcast;
                }
                tempAreas.clear();
            }
            resultBroadcastList.add(maxAreaBroadcast);
            allAreaSet.removeAll(broadcast2AreasMap.get(maxAreaBroadcast));
            maxAreaBroadcast=null;
            maxAreaSize=0;

        }



        return resultBroadcastList;
    }


    public static void putBroadcastInfo(Map<String, Set<String>> broadcast2AreasMap,String broadcastName,String[] areas){
        Set<String> areaSet= Arrays.stream(areas).collect(Collectors.toSet());
        broadcast2AreasMap.put(broadcastName,areaSet);
    }

    public static Set<String> allAreas(Map<String, Set<String>> broadcast2AreasMap){
        return broadcast2AreasMap.values().stream().flatMap(Collection::stream).collect(Collectors.toSet());
    }
}
